// 归并排序 采用自上而下递归
function mergeSort(arr) {
  let len = arr.length
  if (len < 2) {
    return arr
  }
  const mid = Math.floor(len / 2)
  const left = mergeSort(arr.slice(0, mid)) // 分为左小数组
  const right = mergeSort(arr.slice(mid)) // 分为右小数组
  return merge(left, right) // 排序好后归并
}

function merge(left, right) {
  const result = []
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  while (left.length) {
    result.push(left.shift())
  }
  while (right.length) {
    result.push(right.shift())
  }
  return result
}

// 测试用例
const arr = [5, 4, 3, 2, 1]
console.log(mergeSort(arr))